import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
* @description: 127. 单词接龙
* @author hewei
* @date 2022/8/3 15:32
* @version 1.0
*/

public class LadderLength {

    public int ladderLength1(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> set = new HashSet<>(wordList);
        Deque<String> queue = new LinkedList<>();
        HashSet<String> vis = new HashSet<>();
        int ans = 1;
        char[] chars = new char[26];
        if (!set.contains(endWord)) return 0;
        if (beginWord.equals(endWord)) return 1;
        for (int i = 0; i <= 26; i++) chars[i] = (char) (i + 'a');
        queue.add(beginWord);
        vis.add(beginWord);
        while (!queue.isEmpty()) {
            ++ans;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                char[] pollChars = queue.poll().toCharArray();
                for (int j = 0; j < pollChars.length; j++) {
                    char temp = pollChars[j];
                    for (int k = 0; k < chars.length; k++) {
                        if (chars[k] != temp) {
                            pollChars[j] = chars[k];
                            String s = new String(pollChars);
                            pollChars[j] = temp;
                            if (!vis.contains(s) && set.contains(s)) {
                                if (s.equals(endWord)) return ans;
                                vis.add(s);
                                queue.add(s);
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }

    HashSet<String> set;
    char[] nums;
    int count1 = 1;
    int count2 = 1;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        set = new HashSet<>(wordList);
        if (!set.contains(endWord)) return 0;
        if (beginWord.equals(endWord)) return 1;
        HashSet<String> set1 = new HashSet<>();
        HashSet<String> set2 = new HashSet<>();
        Deque<String> queue1 = new LinkedList<>();
        Deque<String> queue2 = new LinkedList<>();
        nums = new char[26];
        queue1.add(beginWord);
        queue2.add(endWord);
        set1.add(beginWord);
        set2.add(endWord);
        for (int i = 0; i < 26; i++) nums[i] = (char) (i + 'a');
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            if (queue1.size() > queue2.size()) {
                if (bfs(queue2, set2, set1, false)) return count1 + count2 - 1;
            } else if (bfs(queue1, set1, set2, true)) return count2 + count1 - 1;
        }
        return 0;
    }

    public boolean bfs(Deque<String> queue, HashSet<String> vis, HashSet<String> other, boolean flag) {
        int size = queue.size();
        if (flag) ++count1;
        else ++count2;
        for (int i = 0; i < size; i++) {
            char[] chars = queue.poll().toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char temp = chars[j];
                for (char num : nums) {
                    if (temp != num) {
                        chars[j] = num;
                        String s = new String(chars);
                        chars[j] = temp;
                        if (!vis.contains(s) && set.contains(s)) {
                            if (other.contains(s)) return true;
                            queue.add(s);
                            vis.add(s);
                        }
                    }
                }
            }
        }
        return false;
    }
}
